//
//  main.c
//  Questions
//
//  Created by wangrui on 14-09-18.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

/*
 *Bellman-Ford最短路径 队列优化
 */


#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#define INF 999999

/*测试数据
 5 7
 1 2 2
 1 5 10
 2 3 3
 2 5 7
 3 4 4
 4 5 5
 5 3 6
*/

typedef struct path{
	int idx;
	struct path *father;
}Path;


int main(int argc, const char * argv[])
{
	int n,m;
	scanf("%d %d",&n,&m);
	
	//使用邻接表存储
	int u[m+1],v[m+1],w[m+1];
	int first[n+1],next[n+1];
	int flag[n+1];//标记点有没有在队列里
	int dis[n+1]; //距离数组,第0个点不使用
	Path pathes[n+1];
	
	//初始化
	for (int i=0; i<n+1; i++) {
		first[i] = -1;
		next[i] = -1;
		flag[i] = 0;
		dis[i] = INF;
		
		//初始化路径指针
		pathes[i].idx = i;
		pathes[i].father = NULL;
	}
	
	//输入边,建立邻接表
	for (int i=1; i<=m; i++) {
		scanf("%d %d %d",&u[i],&v[i],&w[i]);
		next[i] = first[u[i]];
		first[u[i]] = i;
	}
	

	int src,dst;
	printf("输入起点终点:\n");
	scanf("%d %d",&src,&dst);
	
	dis[src] = 0; //设置dis数组起始点到起始点距离为0
	
	
	queue_t que = createQueue();
	
	//第一个点进队列
	enqueue(que, &src);
	flag[src] = 1;
	
	while (!is_empty_queue(que)) {

		const int *out = get_head(que);
		int head = *out;
		int k = first[head]; //head 点对应的第一边
		
		while (k != -1) {
			
			if ( dis[v[k]] > dis[u[k]] + w[k] ) {
				
				dis[v[k]] = dis[u[k]] + w[k];
				pathes[v[k]].father = &pathes[u[k]];
				
				//队列里不存在该点,进队列
				if (flag[v[k]] == 0) {
					
					enqueue(que, &v[k]);
					flag[v[k]] = 1;
				}
			}
			
			k = next[k];
		}
		
		//出队列
		flag[head] = 0;
		dequeue(que, NULL);
	}
	
	
	//打印最短路径
	printf("the shortest distances are:");
	for (int i= 1; i<=n; i++) {
		printf("%d ", dis[i]);
	}
	printf("\n");
	
	printf("the shortest distance is %d \n",dis[dst]);
	printf("the shortest path is:");
	printf("%d",dst);
	
	Path *pa = pathes[dst].father;
	while (pa) {
		printf(" <- %d",pa->idx);
		pa = pa->father;
	}
	printf("\n");
	
	
	return 0;
}


